
<!DOCTYPE HTML>
<html lang="zh-hans" >
    <head>
        <meta charset="UTF-8">
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <title>2.图论例题 · 计算机 ,java , 大数据 基础知识体系</title>
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="description" content="">
        <meta name="generator" content="GitBook 3.2.3">
        <meta name="author" content="hzh">
        
        
    
    <link rel="stylesheet" href="../gitbook/style.css">

    
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-splitter/splitter.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchors/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-anchor-navigation-ex/style/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-toggle-chapters/toggle.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-back-to-top-button/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-code/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-search-pro/search.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-pageview-count/plugin.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-highlight/website.css">
                
            
                
                <link rel="stylesheet" href="../gitbook/gitbook-plugin-fontsettings/website.css">
                
            
        

    

    
        
    

        
    
    
    
    <meta name="HandheldFriendly" content="true"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black">
    <link rel="apple-touch-icon-precomposed" sizes="152x152" href="../gitbook/images/apple-touch-icon-precomposed-152.png">
    <link rel="shortcut icon" href="../gitbook/images/favicon.ico" type="image/x-icon">

    
    <link rel="next" href="3.散列表.html" />
    
    
    <link rel="prev" href="1.图论.html" />
    

    
    
    
    

    </head>
    <body>
        
<div class="book">
    <div class="book-summary">
        
            
<div id="book-search-input" role="search">
    <input type="text" placeholder="输入并搜索" />
</div>

            
                <nav role="navigation">
                


<ul class="summary">
    
    

    

    
        
        <li class="header">操作系统</li>
        
        
    
        <li class="chapter " data-level="1.1" data-path="../">
            
                <a href="../">
            
                    
                    Introduction
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.2" data-path="../操作系统/1.基本概述.html">
            
                <a href="../操作系统/1.基本概述.html">
            
                    
                    1.操作系统基本概述
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.3" data-path="../操作系统/2.进程管理之进程与线程.html">
            
                <a href="../操作系统/2.进程管理之进程与线程.html">
            
                    
                    2.进程管理之进程与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.4" data-path="../操作系统/3.进程管理之处理机调度.html">
            
                <a href="../操作系统/3.进程管理之处理机调度.html">
            
                    
                    3.进程管理之处理机调度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.5" data-path="../操作系统/4.进程管理之进程同步.html">
            
                <a href="../操作系统/4.进程管理之进程同步.html">
            
                    
                    4.进程管理之进程同步
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.6" data-path="../操作系统/5.内存管理之基本概念.html">
            
                <a href="../操作系统/5.内存管理之基本概念.html">
            
                    
                    5.内存管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.7" data-path="../操作系统/6.内存管理之虚拟内存.html">
            
                <a href="../操作系统/6.内存管理之虚拟内存.html">
            
                    
                    6.内存管理之虚拟内存
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.8" data-path="../操作系统/7.IO设备管理之基本概念.html">
            
                <a href="../操作系统/7.IO设备管理之基本概念.html">
            
                    
                    7.IO设备管理之基本概念
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="1.9" data-path="../操作系统/8.面试题总结一.html">
            
                <a href="../操作系统/8.面试题总结一.html">
            
                    
                    8.面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">计算机网络篇</li>
        
        
    
        <li class="chapter " data-level="2.1" data-path="../计算机网络/1.计算机网络入门基础概念.html">
            
                <a href="../计算机网络/1.计算机网络入门基础概念.html">
            
                    
                    1.计算机网络入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.2" data-path="../计算机网络/2.计算机网络通信基础.html">
            
                <a href="../计算机网络/2.计算机网络通信基础.html">
            
                    
                    2.计算机网络通信入门文章(必读)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.3" data-path="../计算机网络/3.数据链路层.html">
            
                <a href="../计算机网络/3.数据链路层.html">
            
                    
                    3.数据链路层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.4" data-path="../计算机网络/4.网络层1.html">
            
                <a href="../计算机网络/4.网络层1.html">
            
                    
                    4.网络层(一)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.5" data-path="../计算机网络/5.网络层2.html">
            
                <a href="../计算机网络/5.网络层2.html">
            
                    
                    5.网络层(二)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.6" data-path="../计算机网络/6.传输层.html">
            
                <a href="../计算机网络/6.传输层.html">
            
                    
                    6.传输层
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.7" data-path="../计算机网络/7.应用层.html">
            
                <a href="../计算机网络/7.应用层.html">
            
                    
                    7.应用层(⭐)
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.8" data-path="../计算机网络/10.HTTP相关协议.html">
            
                <a href="../计算机网络/10.HTTP相关协议.html">
            
                    
                    8.HTTP相关及发展
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="2.9" >
            
                <span>
            
                    
                    9.websocket
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="2.10" data-path="../计算机网络/9.面试题二.html">
            
                <a href="../计算机网络/9.面试题二.html">
            
                    
                    面试题总结一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">数据结构篇</li>
        
        
    
        <li class="chapter " data-level="3.1" data-path="1.图论.html">
            
                <a href="1.图论.html">
            
                    
                    1.图论
            
                </a>
            

            
        </li>
    
        <li class="chapter active" data-level="3.2" data-path="2.图论例题.html">
            
                <a href="2.图论例题.html">
            
                    
                    2.图论例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.3" data-path="3.散列表.html">
            
                <a href="3.散列表.html">
            
                    
                    3.散列表
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.4" data-path="4.排序算法.html">
            
                <a href="4.排序算法.html">
            
                    
                    4.排序算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.5" data-path="5.排序列题.html">
            
                <a href="5.排序列题.html">
            
                    
                    5.排序算法例题
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.6" data-path="6.树论.html">
            
                <a href="6.树论.html">
            
                    
                    6.树论
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.7" data-path="7.树论例题.html">
            
                <a href="7.树论例题.html">
            
                    
                    7.树论例题.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="3.8" data-path="9.模板.html">
            
                <a href="9.模板.html">
            
                    
                    数据结构模板
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">算法篇</li>
        
        
    
        <li class="chapter " data-level="4.1" data-path="../算法/leetCode周赛题解.html">
            
                <a href="../算法/leetCode周赛题解.html">
            
                    
                    leetCode周赛记录
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.2" data-path="../算法/1.时间复杂度.html">
            
                <a href="../算法/1.时间复杂度.html">
            
                    
                    1.时间复杂度
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.3" data-path="../算法/2.深度优先搜索.html">
            
                <a href="../算法/2.深度优先搜索.html">
            
                    
                    2.深度优先搜索算法
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.4" data-path="../算法/2.深度优先搜索题目集.html">
            
                <a href="../算法/2.深度优先搜索题目集.html">
            
                    
                    2.深搜题目集
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="4.5" data-path="../算法/3.广度优先搜索.html">
            
                <a href="../算法/3.广度优先搜索.html">
            
                    
                    3.广度优先搜索算法
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">JVM篇</li>
        
        
    
        <li class="chapter " data-level="5.1" data-path="../jvm/1.jvm内存结构.html">
            
                <a href="../jvm/1.jvm内存结构.html">
            
                    
                    1.jvm内存结构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.2" data-path="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                <a href="../jvm/2.HotSpot虚拟机对象探秘.html">
            
                    
                    2.HotSpot虚拟机对象探秘.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.3" data-path="../jvm/3.对象存亡与垃圾收集算法.html">
            
                <a href="../jvm/3.对象存亡与垃圾收集算法.html">
            
                    
                    3.对象存亡与垃圾收集算法.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.4" data-path="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                <a href="../jvm/4.HotSpot的算法细节与垃圾收集器.html">
            
                    
                    4.HotSpot的算法细节与垃圾收集器.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.5" data-path="../jvm/5.内存分配与回收策略.html">
            
                <a href="../jvm/5.内存分配与回收策略.html">
            
                    
                    5.内存分配与回收策略.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.6" data-path="../jvm/6.类文件结构.html">
            
                <a href="../jvm/6.类文件结构.html">
            
                    
                    6.类文件结构.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.7" data-path="../jvm/7.类加载机制.html">
            
                <a href="../jvm/7.类加载机制.html">
            
                    
                    7.类加载机制.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="5.8" data-path="../jvm/8.jvm逃逸分析.html">
            
                <a href="../jvm/8.jvm逃逸分析.html">
            
                    
                    8.逃逸分析技术
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">多线程篇</li>
        
        
    
        <li class="chapter " data-level="6.1" data-path="../多线程/basic/0.多线程路线图.html">
            
                <a href="../多线程/basic/0.多线程路线图.html">
            
                    
                    1.多线程学习路线图
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.2" data-path="../多线程/basic/0.java内存模型与线程.html">
            
                <a href="../多线程/basic/0.java内存模型与线程.html">
            
                    
                    2.java内存模型与线程
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.3" data-path="../多线程/3.并行程序基础.html">
            
                <a href="../多线程/3.并行程序基础.html">
            
                    
                    2.并行程序基础
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.4" data-path="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                <a href="../多线程/basic/0.jhappenBefore与jvm指令重排.html">
            
                    
                    3.happenBefore与jvm指令重排序
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.5" data-path="../多线程/basic/1.synchronized与volatile.html">
            
                <a href="../多线程/basic/1.synchronized与volatile.html">
            
                    
                    4.synchronized与volatile.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.6" data-path="../多线程/basic/2.ThreadLocal.html">
            
                <a href="../多线程/basic/2.ThreadLocal.html">
            
                    
                    5.ThreadLocal.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.7" data-path="../多线程/cas/1.乐观锁与悲观锁.html">
            
                <a href="../多线程/cas/1.乐观锁与悲观锁.html">
            
                    
                    6.乐观锁与悲观锁.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.8" data-path="../多线程/cas/2.CAS与atomic类.html">
            
                <a href="../多线程/cas/2.CAS与atomic类.html">
            
                    
                    7.CAS与atomic类.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.9" data-path="../多线程/aqs/1.AQS.html">
            
                <a href="../多线程/aqs/1.AQS.html">
            
                    
                    8.AQS.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.10" data-path="../多线程/aqs/2.基于AQS的并发工具.html">
            
                <a href="../多线程/aqs/2.基于AQS的并发工具.html">
            
                    
                    9.基于AQS的并发工具.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.11" data-path="../多线程/blockingQueue/1.阻塞队列.html">
            
                <a href="../多线程/blockingQueue/1.阻塞队列.html">
            
                    
                    10.阻塞队列.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.12" data-path="../多线程/pond/1.线程池与底层原理.html">
            
                <a href="../多线程/pond/1.线程池与底层原理.html">
            
                    
                    11.线程池与底层原理.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.13" data-path="../多线程/10面试题一.html">
            
                <a href="../多线程/10面试题一.html">
            
                    
                    12.面试题一
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="6.14" data-path="../多线程/10面试题二.html">
            
                <a href="../多线程/10面试题二.html">
            
                    
                    13.面试题二.md
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">java集合篇</li>
        
        
    
        <li class="chapter " data-level="7.1" data-path="../basic/collection/1.java集合.html">
            
                <a href="../basic/collection/1.java集合.html">
            
                    
                    1.集合架构
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.2" data-path="../basic/collection/2.HashMap源码分析.html">
            
                <a href="../basic/collection/2.HashMap源码分析.html">
            
                    
                    2.hashMap底层原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="7.3" data-path="../basic/collection/3.ConcurrentHashMap分析.html">
            
                <a href="../basic/collection/3.ConcurrentHashMap分析.html">
            
                    
                    3.ConcurrentHashMap分析
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">设计模式篇</li>
        
        
    
        <li class="chapter " data-level="8.1" >
            
                <span>
            
                    
                    1.创造型模式
            
                </span>
            

            
        </li>
    
        <li class="chapter " data-level="8.2" data-path="../设计模式/factory/三种工厂模式介绍.html">
            
                <a href="../设计模式/factory/三种工厂模式介绍.html">
            
                    
                    三种工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.3" data-path="../设计模式/factory/实战工厂模式.html">
            
                <a href="../设计模式/factory/实战工厂模式.html">
            
                    
                    实战工厂模式
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="8.4" data-path="../设计模式/factory/实战抽象工厂模式.html">
            
                <a href="../设计模式/factory/实战抽象工厂模式.html">
            
                    
                    实战抽象工厂模式
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">mysql篇</li>
        
        
    
        <li class="chapter " data-level="9.1" data-path="../数据库/mysql/1.b树b+树的底层原理.html">
            
                <a href="../数据库/mysql/1.b树b+树的底层原理.html">
            
                    
                    1.mysql索引基础之b树与b+树⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.2" data-path="../数据库/mysql/2.mysql索引.html">
            
                <a href="../数据库/mysql/2.mysql索引.html">
            
                    
                    2.mysql索引及优化⭐⭐⭐⭐
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.3" data-path="../数据库/mysql/3.mysql存储引擎.html">
            
                <a href="../数据库/mysql/3.mysql存储引擎.html">
            
                    
                    3.mysql存储引擎.md
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.4" data-path="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                <a href="../数据库/mysql/4.多版本并发控制之mvcc原理.html">
            
                    
                    4.多版本并发控制之mvcc原理
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.5" data-path="../数据库/mysql/4.mysql事务.html">
            
                <a href="../数据库/mysql/4.mysql事务.html">
            
                    
                    5.mysql事务
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.6" data-path="../数据库/mysql/5.mysql锁机制.html">
            
                <a href="../数据库/mysql/5.mysql锁机制.html">
            
                    
                    6.mysql的锁机制
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="9.7" data-path="../数据库/mysql/6.mysql面试题一.html">
            
                <a href="../数据库/mysql/6.mysql面试题一.html">
            
                    
                    7.mysql面试题一
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高并发中间件篇</li>
        
        
    

    
        
        <li class="header">架构理论篇</li>
        
        
    
        <li class="chapter " data-level="11.1" data-path="../架构/0.架构演进.html">
            
                <a href="../架构/0.架构演进.html">
            
                    
                    1.架构演进
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="11.2" data-path="../架构/0.微服务架构与soa架构.html">
            
                <a href="../架构/0.微服务架构与soa架构.html">
            
                    
                    2.微服务架构与soa架构
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">高可用系统篇</li>
        
        
    
        <li class="chapter " data-level="12.1" data-path="../高可用架构/1.限流.html">
            
                <a href="../高可用架构/1.限流.html">
            
                    
                    1.系统限流
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.2" data-path="../高可用系统/2.服务熔断.html">
            
                <a href="../高可用系统/2.服务熔断.html">
            
                    
                    2.服务熔断
            
                </a>
            

            
        </li>
    
        <li class="chapter " data-level="12.3" data-path="../高可用系统/3.服务降级.html">
            
                <a href="../高可用系统/3.服务降级.html">
            
                    
                    3.服务降级
            
                </a>
            

            
        </li>
    

    
        
        <li class="header">spring-cloud 微服务篇</li>
        
        
    

    

    <li class="divider"></li>

    <li>
        <a href="https://www.gitbook.com" target="blank" class="gitbook-link">
            本书使用 GitBook 发布
        </a>
    </li>
</ul>


                </nav>
            
        
    </div>

    <div class="book-body">
        
            <div class="body-inner">
                
                    

<div class="book-header" role="navigation">
    

    <!-- Title -->
    <h1>
        <i class="fa fa-circle-o-notch fa-spin"></i>
        <a href=".." >2.图论例题</a>
    </h1>
</div>




                    <div class="page-wrapper" tabindex="-1" role="main">
                        <div class="page-inner">
                            
<div id="book-search-results">
    <div class="search-noresults">
    
                                <section class="normal markdown-section">
                                
                                <div id="anchor-navigation-ex-navbar"><i class="fa fa-navicon"></i><ul><ul><li><span class="title-icon "></span><a href="#1&#x56FE;&#x7684;&#x904D;&#x5386;"><b></b>1.&#x56FE;&#x7684;&#x904D;&#x5386;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x751F;&#x5316;&#x5371;&#x673A;"><b></b>1.&#x751F;&#x5316;&#x5371;&#x673A;</a></li><li><span class="title-icon "></span><a href="#2&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;"><b></b>2.&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;</a></li></ul><li><span class="title-icon "></span><a href="#2&#x6700;&#x77ED;&#x8DEF;"><b></b>2.&#x6700;&#x77ED;&#x8DEF;</a></li><ul><li><span class="title-icon "></span><a href="#1-&#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;"><b></b>1. &#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;</a></li><li><span class="title-icon "></span><a href="#2-&#x88AB;gank&#x7684;&#x4E9A;&#x7D22;"><b></b>2. &#x88AB;Gank&#x7684;&#x4E9A;&#x7D22;</a></li></ul><li><span class="title-icon "></span><a href="#3&#x5E76;&#x67E5;&#x96C6;"><b></b>3.&#x5E76;&#x67E5;&#x96C6;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x5408;&#x5E76;&#x8D26;&#x6237;"><b></b>1.&#x5408;&#x5E76;&#x8D26;&#x6237;</a></li><li><span class="title-icon "></span><a href="#2&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;"><b></b>2.&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;</a></li><li><span class="title-icon "></span><a href="#3&#x5197;&#x4F59;&#x8FDE;&#x63A5;"><b></b>3.&#x5197;&#x4F59;&#x8FDE;&#x63A5;</a></li><li><span class="title-icon "></span><a href="#4&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;"><b></b>4.&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;</a></li><li><span class="title-icon "></span><a href="#5&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;"><b></b>5.&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;</a></li><li><span class="title-icon "></span><a href="#6&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;"><b></b>6.&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;</a></li></ul><li><span class="title-icon "></span><a href="#4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><b></b>4.&#x62D3;&#x6251;&#x6392;&#x5E8F;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x8BFE;&#x7A0B;&#x8868;"><b></b>1.&#x8BFE;&#x7A0B;&#x8868;</a></li><li><span class="title-icon "></span><a href="#2&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;"><b></b>2.&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;</a></li><li><span class="title-icon "></span><a href="#3-&#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;"><b></b>3. &#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;</a></li></ul><li><span class="title-icon "></span><a href="#5&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><b></b>5.&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;</a></li><ul><li><span class="title-icon "></span><a href="#1&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;"><b></b>1.&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;</a></li></ul></ul></ul></div><a href="#" id="anchorNavigationExGoTop"><i class="fa fa-arrow-up"></i></a><h2 id="1&#x56FE;&#x7684;&#x904D;&#x5386;"><a name="1&#x56FE;&#x7684;&#x904D;&#x5386;" class="anchor-navigation-ex-anchor" href="#1&#x56FE;&#x7684;&#x904D;&#x5386;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x56FE;&#x7684;&#x904D;&#x5386;" class="plugin-anchor" href="#1&#x56FE;&#x7684;&#x904D;&#x5386;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x56FE;&#x7684;&#x904D;&#x5386;</h2>
<h3 id="1&#x751F;&#x5316;&#x5371;&#x673A;"><a name="1&#x751F;&#x5316;&#x5371;&#x673A;" class="anchor-navigation-ex-anchor" href="#1&#x751F;&#x5316;&#x5371;&#x673A;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x751F;&#x5316;&#x5371;&#x673A;" class="plugin-anchor" href="#1&#x751F;&#x5316;&#x5371;&#x673A;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x751F;&#x5316;&#x5371;&#x673A;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128163946.png" alt="image-20201128163946151"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128163959.png" alt="image-20201128163959391"></p>
<p>&#x53EF;&#x7528;dfs&#x6216;&#x8005;bfs&#x904D;&#x5386;&#x5373;&#x53EF;:</p>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">int</span> m,n,k;
    <span class="hljs-built_in">cin</span>&gt;&gt;m&gt;&gt;n&gt;&gt;k;
    <span class="hljs-built_in">map</span>&lt;<span class="hljs-keyword">int</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; st;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;m ; ++i) {
        st[i]=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;{};
    }
    <span class="hljs-comment">//&#x5B89;&#x5168;&#x57CE;&#x5E02;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span>&gt; isSafe(m, <span class="hljs-literal">false</span>);
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span>&gt; vis(m, <span class="hljs-literal">false</span>);
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; ++i) {
        <span class="hljs-keyword">int</span> temp;
        <span class="hljs-built_in">cin</span>&gt;&gt;temp;
        isSafe[temp]= <span class="hljs-literal">true</span>;
    }
    <span class="hljs-comment">//&#x516C;&#x8DEF;</span>
    <span class="hljs-keyword">int</span> a,b;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt;k ; ++j) {
        <span class="hljs-built_in">cin</span>&gt;&gt;a&gt;&gt;b;
        st[a].push_back(b);
        st[b].push_back(a);
    }
    <span class="hljs-comment">//&#x8D77;&#x6B62;</span>
    <span class="hljs-keyword">int</span> start,end;
    <span class="hljs-built_in">cin</span>&gt;&gt;start&gt;&gt;end;
    <span class="hljs-keyword">if</span>(!isSafe[end]){
        <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;The city &quot;</span>&lt;&lt;end&lt;&lt;<span class="hljs-string">&quot; is not safe!&quot;</span>&lt;&lt;<span class="hljs-built_in">endl</span>;
        <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    }
    <span class="hljs-comment">//&#x961F;&#x5217;</span>
    <span class="hljs-built_in">queue</span>&lt;<span class="hljs-keyword">int</span>&gt; q;
    q.push(start);
    <span class="hljs-keyword">while</span>(!q.empty()){
        <span class="hljs-keyword">int</span> top=q.front();
        q.pop();
        vis[top]= <span class="hljs-literal">true</span>;
        <span class="hljs-keyword">if</span>(top==end){
            <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;The city &quot;</span>&lt;&lt;end&lt;&lt;<span class="hljs-string">&quot; can arrive safely!&quot;</span>&lt;&lt;<span class="hljs-built_in">endl</span>;
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        }
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; st[top].size() ; ++i) {
            <span class="hljs-keyword">int</span> cur=st[top][i];
            <span class="hljs-keyword">if</span>(!vis[cur]&amp;&amp; isSafe[cur]){
                q.push(cur);
            }
        }
    }
    <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-string">&quot;The city &quot;</span>&lt;&lt;end&lt;&lt;<span class="hljs-string">&quot; can not arrive safely!&quot;</span>;

}
</code></pre>
<h3 id="2&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;"><a name="2&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;" class="anchor-navigation-ex-anchor" href="#2&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;" class="plugin-anchor" href="#2&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;"><i class="fa fa-link" aria-hidden="true"></i></a>2.<a href="https://leetcode-cn.com/problems/route-between-nodes-lcci/" target="_blank">&#x8282;&#x70B9;&#x95F4;&#x901A;&#x8DEF;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128202933.png" alt="image-20201128202933429"></p>
<p>&#x8003;&#x5BDF;&#x56FE;&#x7684;&#x904D;&#x5386;:</p>
<pre><code class="lang-c++"><span class="hljs-comment">//bfs&#x7248;&#x672C;:</span>
<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">findWhetherExistsPath</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; graph, <span class="hljs-keyword">int</span> start, <span class="hljs-keyword">int</span> target)</span> </span>{
    <span class="hljs-built_in">unordered_map</span>&lt;<span class="hljs-keyword">int</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; st;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span>&gt; vis(n+<span class="hljs-number">1</span>, <span class="hljs-literal">false</span>);
    <span class="hljs-keyword">for</span>( <span class="hljs-keyword">auto</span> k: graph){
        st[k[<span class="hljs-number">0</span>]].push_back(k[<span class="hljs-number">1</span>]);
    }
    <span class="hljs-built_in">queue</span>&lt;<span class="hljs-keyword">int</span>&gt; qu;
    qu.push(start);
    <span class="hljs-keyword">while</span> ( !qu.empty() ){
        <span class="hljs-keyword">int</span> top=qu.front();
        qu.pop();
        vis[top]= <span class="hljs-literal">true</span>;
        <span class="hljs-keyword">if</span> (top == target )<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;st[top].size();i++){
            <span class="hljs-keyword">if</span>( !vis[st[top][i]]){
                qu.push(st[top][i]);
            }
        }
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
}


<span class="hljs-comment">//dfs&#x7248;&#x672C;:</span>
<span class="hljs-built_in">map</span>&lt;<span class="hljs-keyword">int</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; st;
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span> &gt; flag;
<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">dfs</span><span class="hljs-params">(<span class="hljs-keyword">int</span> cur,<span class="hljs-keyword">int</span> target)</span></span>{
    <span class="hljs-keyword">if</span>(cur==target){
       <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
    }
    flag[cur]= <span class="hljs-literal">true</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;st[cur].size();i++){
        <span class="hljs-keyword">if</span>(!flag[st[cur][i]]){
            <span class="hljs-keyword">if</span>(dfs(st[cur][i],target))<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
        }
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
}
<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">findWhetherExistsPath</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; graph, <span class="hljs-keyword">int</span> start, <span class="hljs-keyword">int</span> target)</span> </span>{
    flag=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span>&gt;(n, <span class="hljs-literal">false</span>);
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;n ; ++i) {
        st[i]=<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;();
    }
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> k:graph){
        st[k[<span class="hljs-number">0</span>]].push_back(k[<span class="hljs-number">1</span>]);
    }
    <span class="hljs-keyword">return</span> dfs(start,target);
}
</code></pre>
<h2 id="2&#x6700;&#x77ED;&#x8DEF;"><a name="2&#x6700;&#x77ED;&#x8DEF;" class="anchor-navigation-ex-anchor" href="#2&#x6700;&#x77ED;&#x8DEF;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x6700;&#x77ED;&#x8DEF;" class="plugin-anchor" href="#2&#x6700;&#x77ED;&#x8DEF;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x6700;&#x77ED;&#x8DEF;</h2>
<h3 id="1-&#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;"><a name="1-&#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;" class="anchor-navigation-ex-anchor" href="#1-&#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1-&#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;" class="plugin-anchor" href="#1-&#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;"><i class="fa fa-link" aria-hidden="true"></i></a>1. <strong>&#x54C8;&#x5229;&#xB7;&#x6CE2;&#x7279;&#x7684;&#x8003;&#x8BD5;</strong></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128164119.png" alt="image-20201128164119865"></p>
<p> <strong>&#x8F93;&#x5165;&#x6837;&#x4F8B;</strong></p>
<pre><code class="lang-in">6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80
</code></pre>
<p><strong>&#x8F93;&#x51FA;&#x6837;&#x4F8B;:</strong></p>
<pre><code class="lang-out">4 70
</code></pre>
<p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;:</strong></p>
<p>&#x7B80;&#x5355;&#x7406;&#x89E3;&#x5C31;&#x662F;:</p>
<p>&#x6BCF;&#x4E2A;&#x8282;&#x70B9;&#x5230;&#x5176;&#x4ED6;&#x8282;&#x70B9;&#x7684;&#x6700;&#x77ED;&#x7684;&#x8DEF;&#x5F84;&#x4E2D;,&#x6700;&#x957F;&#x7684;&#x90A3;&#x4E00;&#x6761;&#x6784;&#x5EFA;&#x4E00;&#x4E2A;&#x96C6;&#x5408;</p>
<p>&#x4ECE;&#x8FD9;&#x4E2A;&#x96C6;&#x5408;&#x4E2D;&#x5BFB;&#x627E;&#x6700;&#x77ED;&#x7684;&#x4E00;&#x8DF3;,&#x4F5C;&#x4E3A;&#x7B54;&#x6848;</p>
<p>&#x8FD9;&#x91CC;&#x7528;&#x7684;&#x662F;floyd&#x6700;&#x77ED;&#x8DEF;&#x7B97;&#x6CD5;</p>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> inf=<span class="hljs-number">1000000</span>;
<span class="hljs-comment">//&#x5BFB;&#x627E;&#x8282;&#x70B9;V&#x5230;&#x5176;&#x4ED6;&#x8282;&#x70B9;&#x7684;&#x6700;&#x957F;&#x8DEF;&#x5F84;</span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; graph,<span class="hljs-keyword">int</span> v)</span></span>{
    <span class="hljs-keyword">int</span> m=<span class="hljs-number">-100000</span>;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;graph.size() ; ++i) {
        <span class="hljs-keyword">if</span>( i!= v){
            m=max(m,graph[v][i]);
        }
    }
    <span class="hljs-keyword">return</span> m;
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">int</span> n,m;
    <span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;m;
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; graph(n+<span class="hljs-number">1</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n+<span class="hljs-number">1</span>,inf));
    <span class="hljs-keyword">int</span> a,b,value;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;m ; ++i) {
        <span class="hljs-built_in">cin</span>&gt;&gt;a&gt;&gt;b&gt;&gt;value;
        graph[a][b]=value;
        graph[b][a]=value;
    }

    <span class="hljs-meta">#floyd&#x6784;&#x5EFA;&#x6700;&#x77ED;&#x8DEF;</span>
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = <span class="hljs-number">1</span>; k &lt;=n ; ++k) {
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;=n ; ++i) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">1</span>; j &lt;=n ; ++j) {
                graph[i][j]=min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
    <span class="hljs-keyword">int</span> ans=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">int</span> maxLen=inf;
    <span class="hljs-meta">#&#x5BFB;&#x627E;&#x7B54;&#x6848;</span>
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++){
        <span class="hljs-keyword">int</span> cur=find(graph,i);
        <span class="hljs-keyword">if</span>(cur&lt;maxLen){
            maxLen=cur;
            ans=i;
        }
    }
    <span class="hljs-keyword">if</span>( maxLen != inf){
        <span class="hljs-built_in">cout</span>&lt;&lt;ans&lt;&lt;<span class="hljs-string">&quot; &quot;</span>&lt;&lt;maxLen;
    }<span class="hljs-keyword">else</span>{
        <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-number">0</span>;
    }
}
</code></pre>
<h3 id="2-&#x88AB;gank&#x7684;&#x4E9A;&#x7D22;"><a name="2-&#x88AB;gank&#x7684;&#x4E9A;&#x7D22;" class="anchor-navigation-ex-anchor" href="#2-&#x88AB;gank&#x7684;&#x4E9A;&#x7D22;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2-&#x88AB;gank&#x7684;&#x4E9A;&#x7D22;" class="plugin-anchor" href="#2-&#x88AB;gank&#x7684;&#x4E9A;&#x7D22;"><i class="fa fa-link" aria-hidden="true"></i></a>2. &#x88AB;Gank&#x7684;&#x4E9A;&#x7D22;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128202242.png" alt="image-20201128202242616"></p>
<p><strong>&#x8F93;&#x5165;&#x793A;&#x4F8B;</strong></p>
<pre><code>5 6 1 5
1 2 5
2 5 5
1 3 3
3 5 7
1 4 1
4 5 9
</code></pre><p><strong>&#x8F93;&#x51FA;&#x793A;&#x4F8B;</strong></p>
<pre><code>10 3
</code></pre><p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;:</strong></p>
<p>&#x9898;&#x76EE;&#x60F3;&#x8BA9;&#x6211;&#x4EEC;&#x627E;&#x6700;&#x77ED;&#x8DEF;&#x5F84;&#x7684;&#x6570;&#x76EE;,&#x9700;&#x8981;&#x6CE8;&#x610F;&#x7684;&#x662F;,&#x4E24;&#x4E2A;&#x8282;&#x70B9;&#x95F4;&#x8BFB;&#x53D6;&#x6570;&#x636E;&#x65F6;&#x76F8;&#x540C;&#x957F;&#x5EA6;&#x7684;&#x8DEF;&#x5F84;&#x4E0D;&#x6B62;&#x4E00;&#x6761;(&#x60F3;&#x4E00;&#x60F3;LOL&#x7684;&#x5730;&#x56FE;),&#x56E0;&#x6B64;&#x5E94;&#x8BE5;&#x4E8B;&#x5148;&#x8BB0;&#x5F55;</p>
<p>&#x5176;&#x6B21;,&#x56E0;&#x4E3A;&#x4E24;&#x8282;&#x70B9;&#x95F4;&#x7684;&#x8DEF;&#x5F84;&#x4E0D;&#x6B62;&#x4E00;&#x6761;,&#x6240;&#x4EE5;&#x5728;&#x8BA1;&#x7B97;&#x7B54;&#x6848;&#x7684;&#x65F6;&#x5019;,&#x5E94;&#x7528;*,&#x800C;&#x4E0D;&#x662F;+</p>
<p>&#x5806;&#x4F18;&#x5316;&#x7248;dijkstra&#x6700;&#x77ED;&#x8DEF;:</p>
<pre><code class="lang-c++"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;bits/stdc++.h&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>{
    <span class="hljs-keyword">int</span> n,m,s,e;
    <span class="hljs-built_in">cin</span>&gt;&gt;n&gt;&gt;m&gt;&gt;s&gt;&gt;e;
    <span class="hljs-keyword">int</span> inf=<span class="hljs-number">0x3f3f3f3f</span>;
    <span class="hljs-keyword">typedef</span> pair&lt;<span class="hljs-keyword">int</span>,<span class="hljs-keyword">int</span>&gt; ll;
    <span class="hljs-comment">//&#x56FE;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; graph(n+<span class="hljs-number">1</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>));
    <span class="hljs-comment">//&#x5806;</span>
    priority_queue&lt;ll,<span class="hljs-built_in">vector</span>&lt;ll&gt;,greater&lt;ll&gt;&gt; st;
    <span class="hljs-comment">//&#x8DDD;&#x79BB;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; dist(n+<span class="hljs-number">1</span>,inf);
    <span class="hljs-comment">//&#x6807;&#x5FD7;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">bool</span>&gt; vis(n+<span class="hljs-number">1</span>, <span class="hljs-literal">false</span>);
    <span class="hljs-comment">//&#x8DEF;&#x5F84;&#x6570;&#x91CF;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; lowestNums(n+<span class="hljs-number">1</span>,<span class="hljs-number">1</span>);
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; roadNums(n+<span class="hljs-number">1</span>,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>));
    <span class="hljs-keyword">int</span> a,b,value;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;m ; ++i) {
        <span class="hljs-built_in">cin</span>&gt;&gt;a&gt;&gt;b&gt;&gt;value;
        <span class="hljs-keyword">if</span> ( ! graph[a][b] || value&lt;graph[a][b] ){
            graph[a][b]=value;
            graph[b][a]=value;
            roadNums[a][b]=<span class="hljs-number">1</span>;
            roadNums[b][a]=<span class="hljs-number">1</span>;
        }<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ( value== graph[a][b] ){
            roadNums[a][b]++;
            roadNums[b][a]++;
        }
    }
    st.push({<span class="hljs-number">0</span>,s});
    dist[s]=<span class="hljs-number">0</span>;
    vis[s]= <span class="hljs-literal">true</span>;
    <span class="hljs-keyword">while</span> ( !st.empty() ){
        ll cur= st.top();
        st.pop();
        vis[cur.second]= <span class="hljs-literal">true</span>;
        <span class="hljs-keyword">for</span>( <span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++){
            <span class="hljs-keyword">if</span>( graph[cur.second][i] &amp;&amp; !vis[i] ){
                <span class="hljs-keyword">if</span>( cur.first+graph[cur.second][i] &lt;dist[i] ){
                    dist[i]= cur.first+graph[cur.second][i];
                    st.push({dist[i],i});
                    lowestNums[i] = lowestNums[cur.second]*roadNums[cur.second][i];
                }
                <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ( cur.first+graph[cur.second][i] == dist[i] ){
                    lowestNums[i] += lowestNums[cur.second]*roadNums[cur.second][i];
                }
            }
        }
    }
    <span class="hljs-built_in">cout</span>&lt;&lt; dist[e]&lt;&lt;<span class="hljs-string">&quot; &quot;</span>&lt;&lt;lowestNums[e];
}
</code></pre>
<h2 id="3&#x5E76;&#x67E5;&#x96C6;"><a name="3&#x5E76;&#x67E5;&#x96C6;" class="anchor-navigation-ex-anchor" href="#3&#x5E76;&#x67E5;&#x96C6;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x5E76;&#x67E5;&#x96C6;" class="plugin-anchor" href="#3&#x5E76;&#x67E5;&#x96C6;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x5E76;&#x67E5;&#x96C6;</h2>
<h3 id="1&#x5408;&#x5E76;&#x8D26;&#x6237;"><a name="1&#x5408;&#x5E76;&#x8D26;&#x6237;" class="anchor-navigation-ex-anchor" href="#1&#x5408;&#x5E76;&#x8D26;&#x6237;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x5408;&#x5E76;&#x8D26;&#x6237;" class="plugin-anchor" href="#1&#x5408;&#x5E76;&#x8D26;&#x6237;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x5408;&#x5E76;&#x8D26;&#x6237;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128205058.png" alt="image-20201128205058574"></p>
<p>&#x5E76;&#x67E5;&#x96C6;,&#x95EE;&#x9898;&#x5728;&#x4E8E;,&#x5982;&#x4F55;&#x8BB0;&#x5F55;&#x4E24;&#x4E2A;&#x5217;&#x8868;&#x662F;&#x5426;&#x662F;&#x540C;&#x4E00;&#x4E2A;&#x4EBA;&#x7684;?</p>
<p>&#x5224;&#x65AD;&#x4F9D;&#x636E;:&#x6709;&#x6CA1;&#x6709;&#x76F8;&#x540C;&#x7684;&#x90AE;&#x7BB1;</p>
<p>&#x6240;&#x4EE5;&#x53EF;&#x4EE5;&#x8FD9;&#x6837;&#x60F3;</p>
<blockquote>
<p>&#x521D;&#x59CB;&#x7248;&#x672C;:</p>
<p>1.&#x5FAA;&#x73AF;&#x6BCF;&#x4E00;&#x4E2A;&#x5217;&#x8868;&#x7684;&#x6BCF;&#x4E00;&#x4E2A;&#x90AE;&#x7BB1;,&#x548C;&#x522B;&#x7684;&#x5217;&#x8868;&#x6BD4;&#x8F83;,&#x662F;&#x5426;&#x5B58;&#x5728;&#x522B;&#x7684;&#x5217;&#x8868;&#x4E2D;</p>
<p>&#x6539;&#x8FDB;:</p>
<p>1.&#x7528;&#x4E00;&#x4E2A;set&#x4FDD;&#x5B58;&#x90AE;&#x7BB1;,&#x5982;&#x679C;&#x90AE;&#x7BB1;&#x6CA1;&#x6709;&#x51FA;&#x73B0;&#x8FC7;,&#x5C31;&#x8BB0;&#x5F55;&#x7B2C;&#x4E00;&#x6B21;&#x51FA;&#x73B0;&#x65F6;&#x7684;&#x7236;&#x7C7B;</p>
<p>2.&#x5982;&#x679C;&#x51FA;&#x73B0;&#x8FC7;,&#x5C31;&#x5408;&#x5E76;&#x4E24;&#x4E2A;&#x7236;&#x7C7B;</p>
</blockquote>
<p>c++;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
  <span class="hljs-keyword">int</span> graph[<span class="hljs-number">10000</span>]={<span class="hljs-number">0</span>};

<span class="hljs-function"><span class="hljs-keyword">int</span>  <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i)</span></span>{
    <span class="hljs-keyword">if</span>(graph[i]==i)<span class="hljs-keyword">return</span> graph[i];
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> graph[i]=find(graph[i]);
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Union</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span></span>{
    <span class="hljs-keyword">int</span> p1=find(i);
    <span class="hljs-keyword">int</span> p2=find(j);
    <span class="hljs-keyword">if</span>(p1!=p2){
        graph[p2]=p1;
    }
}
<span class="hljs-comment">//&#x7528;&#x4E8E;&#x4FDD;&#x5B58;&#x8BE5;&#x90AE;&#x7BB1;&#x662F;&#x5426;&#x6709;&#x51FA;&#x73B0;&#x8FC7;</span>
<span class="hljs-built_in">set</span>&lt;<span class="hljs-built_in">string</span>&gt;isTurn;
<span class="hljs-comment">//&#x7528;&#x4E8E;&#x4FDD;&#x5B58;&#x8BE5;&#x90AE;&#x7BB1;&#x7684;&#x7236;&#x7C7B;</span>
<span class="hljs-built_in">map</span>&lt;<span class="hljs-built_in">string</span>,<span class="hljs-keyword">int</span>&gt; emailFa;
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt;&gt; accountsMerge(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt;&gt;&amp; accounts) {
     <span class="hljs-keyword">int</span> n=accounts.size();
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
         graph[i]=i;
     }
     <span class="hljs-comment">//1.&#x904D;&#x5386;,&#x5408;&#x5E76;</span>
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
         <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;accounts[i].size();j++){
             <span class="hljs-keyword">if</span>(isTurn.count(accounts[i][j])==<span class="hljs-number">0</span>){
                 <span class="hljs-comment">//&#x7B2C;&#x4E00;&#x6B21;&#x51FA;&#x73B0;,&#x5219;&#x4FDD;&#x5B58;&#x8BB0;&#x5F55;</span>
                 isTurn.insert(accounts[i][j]);
                 emailFa[accounts[i][j]]=i;
             }<span class="hljs-keyword">else</span>{
                 <span class="hljs-comment">//&#x5426;&#x5219;,&#x8BF4;&#x660E;&#x540C;&#x4E00;&#x4E2A;&#x4EBA;,&#x5408;&#x5E76;</span>
                   Union(emailFa[accounts[i][j]],i);
             }
         }
     }
     <span class="hljs-comment">//2.&#x5C06;&#x6BCF;&#x4E2A;&#x90AE;&#x7BB1;&#x653E;&#x5230;&#x76F8;&#x5BF9;&#x5E94;&#x7684;&#x7236;&#x7C7B;&#x4E0B;&#x9762;,sort&#x53EF;&#x4EE5;&#x81EA;&#x52A8;&#x6392;&#x5E8F;</span>
     <span class="hljs-built_in">map</span>&lt;<span class="hljs-keyword">int</span>,<span class="hljs-built_in">set</span>&lt;<span class="hljs-built_in">string</span>&gt;&gt; m;
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        <span class="hljs-comment">// cout&lt;&lt;graph[i]&lt;&lt;&quot; &quot;;</span>
         <span class="hljs-keyword">int</span> p=find(i);
          <span class="hljs-keyword">if</span>(m.count(p)==<span class="hljs-number">0</span>)m[p]=<span class="hljs-built_in">set</span>&lt;<span class="hljs-built_in">string</span>&gt;();
         <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;accounts[i].size();j++){
             m[p].insert(accounts[i][j]);
         }
     }
     <span class="hljs-comment">//&#x8F6C;&#x5316;&#x6210;&#x76F8;&#x5E94;&#x7684;&#x7ED3;&#x6784;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt;&gt; result;
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> acc:m){
         <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">string</span>&gt; ans;
         ans.push_back(accounts[acc.first][<span class="hljs-number">0</span>]);
         <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> s:acc.second){
             ans.push_back(s);
         }
         result.push_back(ans);
     }
     <span class="hljs-keyword">return</span> result;
}
};
</code></pre>
<h3 id="2&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;"><a name="2&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;" class="anchor-navigation-ex-anchor" href="#2&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;" class="plugin-anchor" href="#2&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;"><i class="fa fa-link" aria-hidden="true"></i></a>2.&#x79FB;&#x51FA;&#x6700;&#x591A;&#x7684;&#x540C;&#x884C;&#x6216;&#x540C;&#x5217;&#x77F3;&#x5934;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128205813.png" alt="image-20201128205813394"></p>
<p>&#x5E76;&#x67E5;&#x96C6;,&#x5173;&#x952E;&#x8981;&#x627E;&#x51FA;&#x4EC0;&#x4E48;&#x548C;&#x4EC0;&#x4E48;&#x5E76;&#x8D77;&#x6765;</p>
<p>&#x8FD9;&#x4E00;&#x9898;&#x5F88;&#x660E;&#x663E;&#x662F;&#x70B9;&#x548C;&#x70B9;&#x4E4B;&#x95F4;&#x5E76;(&#x6761;&#x4EF6;&#x662F;&#x4E24;&#x4E2A;&#x70B9;&#x7684;&#x884C;&#x6570;&#x6216;&#x5217;&#x6570;&#x76F8;&#x540C;),&#x5E76;&#x4E14;&#x5728;&#x5408;&#x5E76;&#x8FC7;&#x7A0B;&#x4E2D;&#x6C42;&#x51FA;&#x6BCF;&#x4E2A;&#x7C07;&#x4E0B;&#x70B9;&#x7684;&#x6570;&#x91CF;,</p>
<p>&#x6700;&#x540E;&#x7ED3;&#x679C;&#x5C31;&#x662F;&#x6BCF;&#x4E2A;&#x7C07;&#x7684;&#x70B9;&#x7684;&#x6570;&#x91CF;-1,&#x76F8;&#x52A0;&#x8D77;&#x6765;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">int</span> graph[<span class="hljs-number">10000</span>]={<span class="hljs-number">0</span>};
<span class="hljs-keyword">int</span> size[<span class="hljs-number">10000</span>]={<span class="hljs-number">0</span>};
<span class="hljs-function"><span class="hljs-keyword">int</span>  <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i)</span></span>{
    <span class="hljs-keyword">if</span>(graph[i]==i)<span class="hljs-keyword">return</span> graph[i];
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> graph[i]=find(graph[i]);
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Union</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span></span>{
    <span class="hljs-keyword">int</span> p1=find(i);
    <span class="hljs-keyword">int</span> p2=find(j);
    <span class="hljs-keyword">if</span>(p1!=p2){
        <span class="hljs-keyword">if</span>(size[p1]&gt;size[p2]){
            graph[p2]=p1;
            size[p1]+=size[p2];
            size[p2]=<span class="hljs-number">0</span>;
        }<span class="hljs-keyword">else</span>{
            graph[p1]=p2;
            size[p2]+=size[p1];
            size[p1]=<span class="hljs-number">0</span>;
        }
    }
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">removeStones</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; stones)</span> </span>{
    <span class="hljs-keyword">int</span> n=stones.size();
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        graph[i]=i;
        size[i]=<span class="hljs-number">1</span>;
    }
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;n;j++){
            <span class="hljs-keyword">if</span>(i!=j){
                <span class="hljs-keyword">if</span>(stones[i][<span class="hljs-number">0</span>]==stones[j][<span class="hljs-number">0</span>]||stones[i][<span class="hljs-number">1</span>]==stones[j][<span class="hljs-number">1</span>]){
                    Union(i,j);
                }
            }
        }
    }
    <span class="hljs-keyword">int</span> cnt=<span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
        <span class="hljs-comment">//cout&lt;&lt;size[i]&lt;&lt;&quot; &quot;;</span>
        <span class="hljs-keyword">if</span>(size[i]&gt;<span class="hljs-number">0</span>)cnt+=size[i]<span class="hljs-number">-1</span>;
    }
    <span class="hljs-keyword">return</span> cnt;

}

};
</code></pre>
<h3 id="3&#x5197;&#x4F59;&#x8FDE;&#x63A5;"><a name="3&#x5197;&#x4F59;&#x8FDE;&#x63A5;" class="anchor-navigation-ex-anchor" href="#3&#x5197;&#x4F59;&#x8FDE;&#x63A5;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3&#x5197;&#x4F59;&#x8FDE;&#x63A5;" class="plugin-anchor" href="#3&#x5197;&#x4F59;&#x8FDE;&#x63A5;"><i class="fa fa-link" aria-hidden="true"></i></a>3.&#x5197;&#x4F59;&#x8FDE;&#x63A5;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128205835.png" alt="image-20201128205834999"></p>
<p>&#x8FD9;&#x4E2A;&#x95EE;&#x9898;&#x610F;&#x601D;&#x662F;,&#x73B0;&#x5728;&#x6709;&#x4E00;&#x4E2A;&#x65E0;&#x5411;&#x4E14;&#x6709;&#x8FD8;&#x7684;&#x56FE;,&#x5982;&#x4F55;&#x5220;&#x6389;&#x4E00;&#x6761;&#x8FB9;,&#x4F7F;&#x5176;&#x6210;&#x4E3A;&#x65E0;&#x73AF;&#x56FE;</p>
<p>----&gt;&#x4E5F;&#x5373;,&#x5E76;&#x67E5;&#x96C6;&#x5408;&#x5E76;&#x7684;&#x65F6;&#x5019;,&#x5982;&#x679C;&#x53D1;&#x73B0;&#x6709;&#x7956;&#x5148;&#x4F7F;&#x76F8;&#x7B49;&#x7684;,&#x5C31;&#x8BF4;&#x660E;&#x8BE5;&#x6761;&#x8FB9;&#x9020;&#x6210;&#x4E86;&#x73AF;,&#x5219;&#x8BB0;&#x5F55;&#x8BE5;&#x8FB9;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
    <span class="hljs-keyword">int</span> graph[<span class="hljs-number">10000</span>]={<span class="hljs-number">0</span>};
<span class="hljs-keyword">int</span> size[<span class="hljs-number">10000</span>]={<span class="hljs-number">0</span>};
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;result;
<span class="hljs-function"><span class="hljs-keyword">int</span>  <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i)</span></span>{
    <span class="hljs-keyword">if</span>(graph[i]==i)<span class="hljs-keyword">return</span> graph[i];
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> graph[i]=find(graph[i]);
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Union</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span></span>{
    <span class="hljs-keyword">int</span> p1=find(i);
    <span class="hljs-keyword">int</span> p2=find(j);
    <span class="hljs-keyword">if</span>(p1!=p2){
        graph[p2]=p1;
    }<span class="hljs-keyword">else</span>{
        <span class="hljs-comment">//&#x8BF4;&#x660E;&#x53D1;&#x751F;&#x4E86;&#x51B2;&#x7A81;,&#x5219;&#x628A;&#x8BE5;&#x8FB9;&#x52A0;&#x5165;&#x7ED3;&#x679C;&#x96C6;</span>
        result.push_back(i);
        result.push_back(j);
    }
}
<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; findRedundantConnection(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; edges) {
     <span class="hljs-keyword">int</span> n=edges.size();
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;=n;i++){
        graph[i]=i;
     }
     <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++){
         <span class="hljs-keyword">int</span> l1=edges[i][<span class="hljs-number">0</span>];
         <span class="hljs-keyword">int</span> l2=edges[i][<span class="hljs-number">1</span>];
         Union(l1,l2);
     }
     <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; v;
     v.push_back(result[result.size()<span class="hljs-number">-2</span>]);
     v.push_back(result[result.size()<span class="hljs-number">-1</span>]);
     <span class="hljs-keyword">return</span> v;
}

};
</code></pre>
<h3 id="4&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;"><a name="4&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;" class="anchor-navigation-ex-anchor" href="#4&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;" class="plugin-anchor" href="#4&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x88AB;&#x56F4;&#x7ED5;&#x7684;&#x533A;&#x57DF;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128211624.png" alt="image-20201128211624876"></p>
<p>&#x5982;&#x4F55;&#x8FD0;&#x7528;&#x5E76;&#x67E5;&#x96C6;?</p>
<p>1.&#x5C06;&#x4E8C;&#x7EF4;&#x8F6C;&#x5316;&#x4E3A;&#x4E00;&#x7EF4;,&#x5373;i*row+j</p>
<p>2.&#x521B;&#x9020;&#x865A;&#x62DF;&#x8282;&#x70B9;row*col,&#x5C06;&#x8FB9;&#x754C;&#x7684;&#x548C;&#x865A;&#x62DF;&#x8282;&#x70B9;&#x5E76;,&#x82E5;&#x975E;&#x8FB9;&#x754C;,&#x5C31;&#x548C;&#x4E0A;&#x4E0B;&#x5DE6;&#x53F3;&#x5E76;&#x5373;&#x53EF;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">int</span> graph[<span class="hljs-number">10000</span>]={<span class="hljs-number">0</span>};
<span class="hljs-function"><span class="hljs-keyword">int</span>  <span class="hljs-title">find</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i)</span></span>{
    <span class="hljs-keyword">if</span>(graph[i]==i)<span class="hljs-keyword">return</span> graph[i];
    <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> graph[i]=find(graph[i]);
}
<span class="hljs-keyword">int</span> cnt=<span class="hljs-number">0</span>;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Union</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span></span>{
    <span class="hljs-keyword">int</span> p1=find(i);
    <span class="hljs-keyword">int</span> p2=find(j);
    <span class="hljs-keyword">if</span>(p1!=p2){
        graph[p2]=p1;
    }<span class="hljs-keyword">else</span>{
        <span class="hljs-comment">//&#x8BF4;&#x660E;&#x6539;&#x53D8;&#x65E0;&#x9700;&#x5B58;&#x5728;&#x5C31;&#x5DF2;&#x7ECF;&#x8054;&#x901A;,&#x8BA9;&#x53EF;&#x91CD;&#x65B0;&#x64CD;&#x4F5C;&#x7684;&#x6B21;&#x6570;++;</span>
        cnt++;
    }
}
<span class="hljs-function"><span class="hljs-keyword">bool</span>  <span class="hljs-title">connected</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j)</span></span>{
    <span class="hljs-keyword">return</span> find(i)==find(j);
}
<span class="hljs-comment">//&#x53EF;&#x4EE5;&#x5C06;&#x4E8C;&#x7EF4;&#x8F6C;&#x5316;&#x6210;&#x4E00;&#x7EF4;</span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">turnNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> i,<span class="hljs-keyword">int</span> j,<span class="hljs-keyword">int</span> cow)</span></span>{
    <span class="hljs-keyword">return</span> i*cow+j;
}
<span class="hljs-comment">//&#x521D;&#x59CB;&#x5316;&#x51FD;&#x6570;</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">init</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span>{
    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;n;i++)graph[i]=i;
}
<span class="hljs-keyword">int</span> direction[<span class="hljs-number">4</span>][<span class="hljs-number">2</span>]={<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">-1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">0</span>,<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">-1</span>};
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">solve</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">char</span>&gt;&gt;&amp; board)</span> </span>{
   <span class="hljs-keyword">int</span> row=board.size();
   <span class="hljs-keyword">if</span>(row==<span class="hljs-number">0</span>)<span class="hljs-keyword">return</span>;
   <span class="hljs-keyword">int</span> col=board[<span class="hljs-number">0</span>].size();
   init(row*col+<span class="hljs-number">1</span>);
   <span class="hljs-comment">//&#x521B;&#x5EFA;&#x4E00;&#x4E2A;&#x865A;&#x62DF;&#x8282;&#x70B9;,&#x7528;&#x4E8E;&#x8FDE;&#x63A5;&#x8FB9;&#x754C;&#x7684;O</span>
   <span class="hljs-keyword">int</span> virtualNode=row*col;
   <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;row;i++){
       <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;col;j++){
           <span class="hljs-keyword">if</span>(board[i][j]==<span class="hljs-string">&apos;O&apos;</span>){
               <span class="hljs-keyword">if</span>(i==<span class="hljs-number">0</span>||i==row<span class="hljs-number">-1</span>||j==<span class="hljs-number">0</span>||j==col<span class="hljs-number">-1</span>){
                   <span class="hljs-comment">//&#x5982;&#x679C;&#x662F;&#x8FB9;&#x754C;&#x7684;&#x4E00;&#x4E2A;&#x70B9;,&#x5C31;&#x548C;&#x865A;&#x62DF;&#x8282;&#x70B9;&#x5E76;</span>
                   Union(virtualNode,turnNode(i,j,row));
               }<span class="hljs-keyword">else</span>{
                   <span class="hljs-comment">//&#x5426;&#x5219;&#x5C31;&#x548C;&#x4E0A;&#x4E0B;&#x5DE6;&#x53F3;&#x5E76;</span>
                   <span class="hljs-keyword">for</span>(<span class="hljs-keyword">auto</span> k:direction){
                       <span class="hljs-keyword">int</span> lx=i+k[<span class="hljs-number">0</span>];
                       <span class="hljs-keyword">int</span> ly=j+k[<span class="hljs-number">1</span>];
                       <span class="hljs-keyword">if</span>(lx&gt;=<span class="hljs-number">0</span>&amp;&amp;lx&lt;row&amp;&amp;ly&gt;=<span class="hljs-number">0</span>&amp;&amp;ly&lt;col&amp;&amp;board[lx][ly]==<span class="hljs-string">&apos;O&apos;</span>){
                           Union(turnNode(i,j,row),turnNode(lx,ly,row));
                       }
                   }
               }
           }
       }
   }
   <span class="hljs-comment">//&#x586B;&#x5145;,&#x5982;&#x679C;&#x7236;&#x7C7B;&#x4E3A;&#x865A;&#x62DF;node,&#x5219;&#x4E0D;&#x53D8;,&#x5426;&#x5219;&#x4E3A;x</span>
   <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>;i&lt;row;i++){
       <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">0</span>;j&lt;col;j++){
           <span class="hljs-built_in">cout</span>&lt;&lt;graph[turnNode(i,j,row)]&lt;&lt;<span class="hljs-string">&quot; &quot;</span>;
           <span class="hljs-keyword">if</span>(!connected(virtualNode,turnNode(i,j,row))){
               board[i][j]=<span class="hljs-string">&apos;X&apos;</span>;
           }
       }
       <span class="hljs-built_in">cout</span>&lt;&lt;<span class="hljs-built_in">endl</span>;
   }
}
</code></pre>
<h3 id="5&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;"><a name="5&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;" class="anchor-navigation-ex-anchor" href="#5&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;" class="plugin-anchor" href="#5&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;"><i class="fa fa-link" aria-hidden="true"></i></a>5.&#x7EDF;&#x8BA1;&#x53C2;&#x4E0E;&#x901A;&#x4FE1;&#x7684;&#x670D;&#x52A1;&#x5668;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128211558.png" alt="image-20201128211558849"></p>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128211606.png" alt="image-20201128211606774"></p>
<p>&#x5E76;&#x67E5;&#x96C6;,&#x5148;&#x7B97;&#x6BCF;&#x4E00;&#x884C;,&#x6BCF;&#x4E00;&#x5217;,&#x7B2C;&#x4E00;&#x6B21;&#x51FA;&#x73B0;&#x7684;1&#x7684;&#x4E0B;&#x6807;</p>
<p>&#x63A5;&#x7740;,&#x540E;&#x9762;&#x7684;&#x7535;&#x8111;&#x53EA;&#x9700;&#x8981;&#x5E76;&#x5230;&#x524D;&#x9762;&#x8BB0;&#x5F55;&#x7684;&#x7B2C;&#x4E00;&#x6B21;&#x51FA;&#x73B0;&#x7684;&#x7236;&#x7C7B;&#x5373;&#x53EF;</p>
<p>&#x7528;size&#x4EE3;&#x8868;&#x8BE5;&#x7C07;&#x7684;&#x5927;&#x5C0F;</p>
<pre><code>class Solution {
public:
int graph[1000000]={0};
int size[1000000]={0};
//&#x67E5;&#x627E;
int  find(int i){
    if(graph[i]==i)return graph[i];
    else return graph[i]=find(graph[i]);
}
//&#x5408;&#x5E76;
void Union(int i,int j){
    int p1=find(i);
    int p2=find(j);
    if(p1!=p2){
        graph[p2]=p1;
        size[p1]+=size[p2];
         size[p2]=0;
    }
}
bool  connected(int i,int j){
    return find(i)==find(j);
}
//&#x53EF;&#x4EE5;&#x5C06;&#x4E8C;&#x7EF4;&#x8F6C;&#x5316;&#x6210;&#x4E00;&#x7EF4;
int node(int i,int j,int cow){
    return i*cow+j;
}
//&#x521D;&#x59CB;&#x5316;&#x51FD;&#x6570;
void init(int n){
    for(int i=0;i&lt;n;i++){
        graph[i]=i;
        size[i]=1;
    }
}
int countServers(vector&lt;vector&lt;int&gt;&gt;&amp; grid) {
    int rows=grid.size();
    int cols=grid[0].size();
   // cout&lt;&lt;rows&lt;&lt;&quot; &quot;&lt;&lt;cols;
    init(rows*cols);
    map&lt;int,int&gt; row;
    map&lt;int,int&gt;col;
    for(int i=0;i&lt;rows;i++){
        for(int j=0;j&lt;cols;j++){
            if(grid[i][j]){
                //&#x8BB0;&#x5F55;&#x6BCF;&#x4E2A;&#x884C;,&#x5217;&#x7B2C;&#x4E00;&#x6B21;&#x51FA;&#x73B0;&#x7684;&#x4F4D;&#x7F6E;
                if(row.count(i)==0)row[i]=j;
                if(col.count(j)==0)col[j]=i;
            }
        }
    }
    //&#x5408;&#x5E76;
    int s=grid[0].size();
    for(int i=0;i&lt;rows;i++){
        for(int j=0;j&lt;cols;j++){
            if(grid[i][j]){
                if(row.count(i)){
                    Union(node(i,row[i],s),node(i,j,s));
                }
                if(col.count(j)){
                    Union(node(col[j],j,s),node(i,j,s));
                }
            }
        }
    }
    int cnt=0;
    for(int i=0;i&lt;rows*cols;i++){
        cout&lt;&lt;size[i]&lt;&lt;&quot; &quot;;
        if(size[i]&gt;1)cnt+=size[i];
    }
    return cnt;
}
};
</code></pre><h3 id="6&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;"><a name="6&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;" class="anchor-navigation-ex-anchor" href="#6&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="6&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;" class="plugin-anchor" href="#6&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;"><i class="fa fa-link" aria-hidden="true"></i></a>6.&#x4FDD;&#x8BC1;&#x56FE;&#x53EF;&#x4EE5;&#x904D;&#x5386;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128211512.png" alt="image-20201128211512765"></p>
<p><img src="D:\Typora\&#x7B97;&#x6CD5;&#x548C;&#x6570;&#x636E;&#x7ED3;&#x6784;\&#x56FE;&#x7B97;&#x6CD5;\assets\1599381490231.png" alt="59938149023"></p>
<p>&#x56FE;&#x4E2D;&#x6709;&#x4E09;&#x79CD;&#x7C7B;&#x578B;&#x7684;&#x8FB9;</p>
<p>&#x5BF9;&#x4E8E;Alice&#x800C;&#x8A00;,&#x5979;&#x53EF;&#x4EE5;&#x8D70;&#x7C7B;&#x578B;&#x4E00;&#x548C;1&#x548C;3,</p>
<p>Bob&#x53EF;&#x4EE5;&#x8D70;2&#x548C;3</p>
<p>&#x56E0;&#x6B64;,&#x6211;&#x4EEC;&#x53EF;&#x4EE5;&#x5148;&#x5C06;&#x7C7B;&#x578B;&#x4E3A;3&#x7684;&#x8FB9;&#x5408;&#x5E76;,</p>
<p>&#x518D;&#x5728;3&#x5408;&#x5E76;&#x540E;&#x7684;&#x57FA;&#x7840;&#x4E0A;,&#x5206;&#x522B;&#x5408;&#x5E76;1&#x548C;2,&#x4E5F;&#x5373;,&#x5206;&#x522B;&#x6784;&#x5EFA;&#x5C5E;&#x4E8E;Bob&#x548C;Alice&#x7684;&#x5E76;&#x67E5;&#x96C6;,</p>
<p>&#x5982;&#x679C;&#x5728;&#x5408;&#x5E76;&#x8FC7;&#x7A0B;&#x4E2D;,&#x53D1;&#x73B0;&#x4E24;&#x4E2A;&#x70B9;&#x65E0;&#x6CD5;&#x5408;&#x5E76;,&#x5C31;&#x8BF4;&#x660E;&#x8FD9;&#x6761;&#x8FB9;&#x53EF;&#x4EE5;&#x5220;&#x9664;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getRoot</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; par,<span class="hljs-keyword">int</span> x)</span></span>{
        <span class="hljs-keyword">int</span> root = x;
        <span class="hljs-keyword">while</span>(par[root]!=root){
            root = par[root];
        }
        <span class="hljs-keyword">while</span>(par[x]!=root){
            <span class="hljs-keyword">int</span> tmp = par[x];
            par[x] = root;
            x = tmp;
        }
        <span class="hljs-keyword">return</span> root;
    }
    <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">merge</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; par,<span class="hljs-keyword">int</span> x,<span class="hljs-keyword">int</span> y)</span></span>{
        <span class="hljs-keyword">int</span> _x = getRoot(par,x);
        <span class="hljs-keyword">int</span> _y = getRoot(par,y);
        <span class="hljs-keyword">if</span>(_x!=_y){
            par[_x]=_y;
            <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
        }
        <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    }
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">maxNumEdgesToRemove</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; edges)</span> </span>{
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;par1 = <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>);
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;par2;
        <span class="hljs-keyword">int</span> ans = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">int</span> cnt1 = n,cnt2;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i =<span class="hljs-number">1</span>;i&lt;=n;i++){
            par1[i] = i;
        }
        <span class="hljs-comment">//&#x5148;&#x6DFB;&#x52A0;&#x7B2C;&#x4E09;&#x79CD;&#x7C7B;&#x578B;&#x7684;&#x8FB9;</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;i&lt;edges.size();i++){
            <span class="hljs-keyword">if</span>(edges[i][<span class="hljs-number">0</span>]==<span class="hljs-number">3</span>){
                <span class="hljs-keyword">if</span>(!merge(par1,edges[i][<span class="hljs-number">1</span>],edges[i][<span class="hljs-number">2</span>]))
                    ans++;
                <span class="hljs-keyword">else</span>
                    cnt1--;
            }
        }
        par2 = par1;
        cnt2 = cnt1;
        <span class="hljs-comment">//&#x518D;&#x6DFB;&#x52A0;&#x5176;&#x4F59;&#x4E24;&#x79CD;&#x7C7B;&#x578B;&#x7684;&#x8FB9;</span>
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;i&lt;edges.size();i++){
            <span class="hljs-keyword">if</span>(edges[i][<span class="hljs-number">0</span>]==<span class="hljs-number">1</span>){
                <span class="hljs-keyword">if</span>(!merge(par1,edges[i][<span class="hljs-number">1</span>],edges[i][<span class="hljs-number">2</span>]))
                    ans++;
                <span class="hljs-keyword">else</span>
                    cnt1--;
            }<span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span>(edges[i][<span class="hljs-number">0</span>]==<span class="hljs-number">2</span>){
                <span class="hljs-keyword">if</span>(!merge(par2,edges[i][<span class="hljs-number">1</span>],edges[i][<span class="hljs-number">2</span>]))
                    ans++;
                <span class="hljs-keyword">else</span>
                    cnt2--;
            }
        }
        <span class="hljs-comment">//&#x5982;&#x679C;&#x8FDE;&#x901A;&#x96C6;&#x4E0D;&#x4E3A;1,&#x5C31;&#x8BF4;&#x660E;&#x4E0D;&#x80FD;&#x5B8C;&#x5168;&#x904D;&#x5386;</span>
        <span class="hljs-keyword">if</span>(cnt1!=<span class="hljs-number">1</span>||cnt2!=<span class="hljs-number">1</span>)
            <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>;
        <span class="hljs-keyword">return</span> ans;
    }
};
</code></pre>
<h2 id="4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><a name="4&#x62D3;&#x6251;&#x6392;&#x5E8F;" class="anchor-navigation-ex-anchor" href="#4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="4&#x62D3;&#x6251;&#x6392;&#x5E8F;" class="plugin-anchor" href="#4&#x62D3;&#x6251;&#x6392;&#x5E8F;"><i class="fa fa-link" aria-hidden="true"></i></a>4.&#x62D3;&#x6251;&#x6392;&#x5E8F;</h2>
<h3 id="1&#x8BFE;&#x7A0B;&#x8868;"><a name="1&#x8BFE;&#x7A0B;&#x8868;" class="anchor-navigation-ex-anchor" href="#1&#x8BFE;&#x7A0B;&#x8868;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x8BFE;&#x7A0B;&#x8868;" class="plugin-anchor" href="#1&#x8BFE;&#x7A0B;&#x8868;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x8BFE;&#x7A0B;&#x8868;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128203804.png" alt="59410727664"></p>
<p>&#x6A21;&#x677F;&#x9898;:</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
<span class="hljs-keyword">public</span>:
<span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">canFinish</span><span class="hljs-params">(<span class="hljs-keyword">int</span> numCourses, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;&amp; prerequisites)</span> </span>{
    <span class="hljs-comment">//&#x4EE3;&#x8868;&#x5165;&#x5EA6;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; in(numCourses,<span class="hljs-number">0</span>);
    <span class="hljs-comment">//&#x90BB;&#x63A5;&#x8868;</span>
    <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt; st(numCourses,<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;{});
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;prerequisites.size() ; ++i) {
        in[prerequisites[i][<span class="hljs-number">0</span>]]++;
        st[prerequisites[i][<span class="hljs-number">1</span>]].push_back(prerequisites[i][<span class="hljs-number">0</span>]);
    }
    <span class="hljs-built_in">queue</span>&lt;<span class="hljs-keyword">int</span>&gt; q;
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt;numCourses ; ++j) {
        <span class="hljs-keyword">if</span>(!in[j])q.push(j);
    }
    <span class="hljs-keyword">while</span>(!q.empty()){
        <span class="hljs-keyword">int</span> top=q.front();
        q.pop();
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;st[top].size() ; ++i) {
            in[st[top][i]]--;
            <span class="hljs-keyword">if</span>(!in[st[top][i]]){
                q.push(st[top][i]);
            }
        }
    }
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> k = <span class="hljs-number">0</span>; k &lt;numCourses ; ++k) {
        <span class="hljs-keyword">if</span>(in[k])<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    }
    <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
}
};
</code></pre>
<h3 id="2&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;"><a name="2&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;" class="anchor-navigation-ex-anchor" href="#2&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="2&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;" class="plugin-anchor" href="#2&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;"><i class="fa fa-link" aria-hidden="true"></i></a><a href="https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/" target="_blank">2.&#x77E9;&#x9635;&#x4E2D;&#x7684;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;</a></h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128204842.png" alt="image-20201128204842197"></p>
<p>&#x8FD9;&#x662F;&#x4E00;&#x9053;&#x52A8;&#x6001;&#x89C4;&#x5212;&#x7684;&#x9898;&#x76EE;,&#x4F46;&#x7528;&#x62D3;&#x6251;&#x6392;&#x5E8F;&#x66F4;&#x65B9;&#x4FBF;</p>
<p>&#x8981;&#x6C42;&#x6700;&#x957F;&#x9012;&#x589E;&#x8DEF;&#x5F84;,&#x6BD4;&#x5982;&#x4ECE;&#x6700;&#x6709;&#x4E0B;&#x89D2;&#x7684;&#x4E24;&#x4E2A;1,</p>
<p>1-&gt;8</p>
<p>1-&gt;{6,2}</p>
<p>&#x5176;&#x5B9E;&#x8FD9;&#x91CC;&#x7684;1&#x76F8;&#x5F53;&#x4E8E;&#x7B2C;&#x4E00;&#x5C42;</p>
<p>&#x63A5;&#x7740;2,6,8&#x5C31;&#x662F;&#x7B2C;&#x4E8C;&#x5C42;</p>
<p>..</p>
<p>..</p>
<p>&#x6240;&#x4EE5;,&#x6700;&#x957F;&#x7684;&#x8DEF;&#x5F84;&#x5176;&#x5B9E;&#x5C31;&#x662F;&#x7B97;&#x5C42;&#x6570;,</p>
<p>&#x5373;,&#x6BCF;&#x6B21;&#x62D3;&#x6251;&#x6392;&#x5E8F;&#x904D;&#x5386;&#x7684;&#x662F;&#x4E00;&#x6574;&#x5C42;&#x7684;&#x6570;&#x636E;,&#x800C;&#x4E0D;&#x662F;&#x4E00;&#x4E2A;&#x4E2A;&#x904D;&#x5386;</p>
<pre><code class="lang-c++"><span class="hljs-keyword">class</span> Solution {
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">longestIncreasingPath</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[][] matrix)</span> </span>{
        <span class="hljs-keyword">if</span> (matrix==null||matrix.length==<span class="hljs-number">0</span>){
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        }        
        <span class="hljs-keyword">int</span>[][] count = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[matrix.length][matrix[<span class="hljs-number">0</span>].length];

        <span class="hljs-comment">//&#x7EDF;&#x8BA1;&#x6BCF;&#x4E2A;&#x70B9;&#x7684;&#x5165;&#x5EA6;&#x7528;count&#x6570;&#x7EC4;&#x4FDD;&#x5B58;&#xFF0C;&#x56E0;&#x4E3A;&#x662F;&#x9012;&#x589E;&#xFF0C;&#x6240;&#x4EE5;&#x5982;&#x679C;&#x5728;&#x4E0A;&#x4E0B;&#x5DE6;&#x53F3;&#xFF0C;&#x6BCF;&#x53D1;&#x73B0;&#x4E00;&#x4E2A;&#x6BD4;&#x5F53;&#x524D;&#x70B9;&#x5C0F;&#x7684;&#x6570;&#xFF0C;&#x5F53;&#x524D;&#x70B9;&#x5165;&#x5EA6;+1</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; matrix.length; i++) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; matrix[i].length; j++) {
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span>[] d : direction) {
                    <span class="hljs-keyword">if</span> (longestIncreasingPathVerify(matrix, i + d[<span class="hljs-number">0</span>], j + d[<span class="hljs-number">1</span>]) &amp;&amp; matrix[i + d[<span class="hljs-number">0</span>]][j + d[<span class="hljs-number">1</span>]] &lt; matrix[i][j]) {
                        count[i][j]++;
                    }
                }
            }
        }
        Deque&lt;<span class="hljs-keyword">int</span>[]&gt; <span class="hljs-built_in">deque</span> = <span class="hljs-keyword">new</span> LinkedList&lt;&gt;();
        <span class="hljs-comment">//count&#x6570;&#x7EC4;&#x4E2D;&#x6240;&#x6709;&#x5165;&#x5EA6;&#x4E3A;0&#x7684;&#x70B9;&#x52A0;&#x5165;&#x961F;&#x5217;</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; count.length; i++) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; count[i].length; j++) {
                <span class="hljs-keyword">if</span> (count[i][j] == <span class="hljs-number">0</span>) {
                    <span class="hljs-built_in">deque</span>.add(<span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{i, j});
                }
            }
        }
        <span class="hljs-keyword">int</span> ans = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">while</span> (!<span class="hljs-built_in">deque</span>.isEmpty()) {
            ans++;
            <span class="hljs-comment">//&#x8FD9;&#x4E2A;&#x8DDF;&#x8BFE;&#x7A0B;&#x8868;I&#x90A3;&#x4E2A;&#x9898;&#x4E0D;&#x4E00;&#x6837;&#xFF0C;&#x9700;&#x8981;&#x4E00;&#x5C42;&#x4E00;&#x5C42;&#x7684;&#x51FA;&#x5217;&#xFF0C;&#x800C;&#x4E0D;&#x662F;&#x4E00;&#x4E2A;&#x4E00;&#x4E2A;&#x7684;&#x51FA;&#xFF0C;&#x56E0;&#x4E3A;&#x8BFE;&#x7A0B;&#x8868;&#x90A3;&#x4E2A;&#x4E0D;&#x5173;&#x5FC3;&#x961F;&#x5217;&#x957F;&#x5EA6;</span>
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> size = <span class="hljs-built_in">deque</span>.size(); size &gt; <span class="hljs-number">0</span>; size--) {
                <span class="hljs-keyword">int</span>[] poll = <span class="hljs-built_in">deque</span>.poll();
                <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span>[] d : direction) {
                    <span class="hljs-keyword">if</span> (longestIncreasingPathVerify(matrix, poll[<span class="hljs-number">0</span>] + d[<span class="hljs-number">0</span>], poll[<span class="hljs-number">1</span>] + d[<span class="hljs-number">1</span>]) &amp;&amp; matrix[poll[<span class="hljs-number">0</span>] + d[<span class="hljs-number">0</span>]][poll[<span class="hljs-number">1</span>] + d[<span class="hljs-number">1</span>]] &gt; matrix[poll[<span class="hljs-number">0</span>]][poll[<span class="hljs-number">1</span>]]) {
                        <span class="hljs-keyword">if</span> (--count[poll[<span class="hljs-number">0</span>] + d[<span class="hljs-number">0</span>]][poll[<span class="hljs-number">1</span>] + d[<span class="hljs-number">1</span>]] == <span class="hljs-number">0</span>) {
                            <span class="hljs-built_in">deque</span>.add(<span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[]{poll[<span class="hljs-number">0</span>] + d[<span class="hljs-number">0</span>], poll[<span class="hljs-number">1</span>] + d[<span class="hljs-number">1</span>]});
                        }
                    }
                }
            }
        }
        <span class="hljs-keyword">return</span> ans;
    }

    <span class="hljs-function"><span class="hljs-keyword">private</span> boolean <span class="hljs-title">longestIncreasingPathVerify</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[][] matrix, <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>{
        <span class="hljs-keyword">return</span> i &gt;= <span class="hljs-number">0</span> &amp;&amp; j &gt;= <span class="hljs-number">0</span> &amp;&amp; i &lt; matrix.length &amp;&amp; j &lt; matrix[i].length;
    }
}
</code></pre>
<h3 id="3-&#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;"><a name="3-&#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;" class="anchor-navigation-ex-anchor" href="#3-&#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="3-&#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;" class="plugin-anchor" href="#3-&#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;"><i class="fa fa-link" aria-hidden="true"></i></a><a href="https://leetcode-cn.com/problems/loud-and-rich/" target="_blank">3. &#x55A7;&#x95F9;&#x548C;&#x5BCC;&#x6709;</a></h3>
<p><img src="C:\Users\86180\AppData\Roaming\Typora\typora-user-images\image-20201226135551142.png" alt="image-20201226135551142"></p>
<h2 id="5&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><a name="5&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;" class="anchor-navigation-ex-anchor" href="#5&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="5&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;" class="plugin-anchor" href="#5&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;"><i class="fa fa-link" aria-hidden="true"></i></a>5.&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;</h2>
<h3 id="1&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;"><a name="1&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;" class="anchor-navigation-ex-anchor" href="#1&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;"><i class="fa fa-link" aria-hidden="true"></i></a><a name="1&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;" class="plugin-anchor" href="#1&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;"><i class="fa fa-link" aria-hidden="true"></i></a>1.&#x516C;&#x8DEF;&#x6751;&#x6751;&#x901A;</h3>
<p><img src="https://gitee.com/zisuu/picture/raw/master/img/20201128164650.png" alt="image-20201128164650329"></p>
<p><strong>&#x8F93;&#x5165;&#x6837;&#x4F8B;:</strong></p>
<pre><code class="lang-in">6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
</code></pre>
<p><strong>&#x8F93;&#x51FA;</strong>:</p>
<pre><code>10
</code></pre><p><strong>&#x9898;&#x76EE;&#x5206;&#x6790;</strong></p>
<p>&#x5C31;&#x662F;&#x6839;&#x636E;&#x6240;&#x6709;&#x7684;&#x8FB9;,&#x6784;&#x5EFA;&#x4E00;&#x9897;&#x6700;&#x5C0F;&#x751F;&#x6210;&#x6811;,&#x4F7F;&#x6240;&#x9700;&#x8D39;&#x7528;&#x6700;&#x4F4E;,&#x8FD9;&#x91CC;&#x7528;&#x7684;&#x662F;Kruskal &#x7B97;&#x6CD5;:</p>
<pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
//&#x7ED3;&#x6784;Edge &#x4EE3;&#x8868;&#x8FB9;
struct Edge{
    int a,b,w;
    Edge(int a,int b ,int w):a(a),b(b),w(w){}
    bool operator &lt; (Edge o)const{
        return w&lt;o.w;
    }
};
vector&lt;Edge&gt; g;
vector&lt;int&gt; fa;
//&#x5E76;&#x67E5;&#x96C6;&#x8DEF;&#x5F84;&#x538B;&#x7F29;&#x67E5;&#x627E;
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
//kruska&#x7B97;&#x6CD5;
int kruska(int n){
    sort(g.begin(),g.end());
    int ans=0;
    int cnt=n;
    for(Edge e:g){
        int fax= find(e.a);
        int fay= find(e.b);
        if(fax!=fay){
            cnt--;
            fa[fax]=fay;
            ans+=e.w;
        }
    }
    return cnt==1?ans:-1;
}
int main(){
    int n,m;
    cin&gt;&gt;n&gt;&gt;m;
    int a,b,value;
    fa=vector&lt;int&gt;(n+1,0);
    for (int i = 1; i &lt;=n ; ++i) {
        fa[i]=i;
    }
    for(int i=0;i&lt;m;i++){
        cin&gt;&gt;a&gt;&gt;b&gt;&gt;value;
        g.push_back(Edge(a,b,value));
    }
    cout&lt;&lt;kruskal(n);
}
</code></pre>
<script>console.log("plugin-popup....");document.onclick = function(e){ e.target.tagName === "IMG" && window.open(e.target.src,e.target.src)}</script><style>img{cursor:pointer}</style>
                                
                                </section>
                            
    </div>
    <div class="search-results">
        <div class="has-results">
            
            <h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
            <ul class="search-results-list"></ul>
            
        </div>
        <div class="no-results">
            
            <h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
            
        </div>
    </div>
</div>

                        </div>
                    </div>
                
            </div>

            
                
                <a href="1.图论.html" class="navigation navigation-prev " aria-label="Previous page: 1.图论">
                    <i class="fa fa-angle-left"></i>
                </a>
                
                
                <a href="3.散列表.html" class="navigation navigation-next " aria-label="Next page: 3.散列表">
                    <i class="fa fa-angle-right"></i>
                </a>
                
            
        
    </div>

    <script>
        var gitbook = gitbook || [];
        gitbook.push(function() {
            gitbook.page.hasChanged({"page":{"title":"2.图论例题","level":"3.2","depth":1,"next":{"title":"3.散列表","level":"3.3","depth":1,"path":"数据结构/3.散列表.md","ref":"数据结构/3.散列表.md","articles":[]},"previous":{"title":"1.图论","level":"3.1","depth":1,"path":"数据结构/1.图论.md","ref":"数据结构/1.图论.md","articles":[]},"dir":"ltr"},"config":{"plugins":["-sharing","splitter","expandable-chapters-small","anchors","sharing-plus","anchor-navigation-ex","favicon","expandable-chapters","toggle-chapters","back-to-top-button","code","-lunr","-search","search-pro","pageview-count","popup","livereload"],"styles":{"website":"./styles/website.css"},"pluginsConfig":{"livereload":{},"splitter":{},"search-pro":{},"sharing-plus":{"qq":false,"all":["facebook","google","twitter","instapaper","linkedin","pocket","stumbleupon"],"douban":false,"facebook":true,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":true,"messenger":false,"line":false,"vk":false,"pocket":true,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"popup":{},"code":{"copyButtons":true},"fontsettings":{"theme":"white","family":"sans","size":2},"highlight":{},"anchor-navigation-ex":{"associatedWithSummary":true,"float":{"floatIcon":"fa fa-navicon","level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"mode":"float","multipleH1":true,"pageTop":{"level1Icon":"","level2Icon":"","level3Icon":"","showLevelIcon":false},"printLog":false,"showGoTop":true,"showLevel":false},"favicon":{},"back-to-top-button":{},"pageview-count":{},"expandable-chapters-small":{},"sharing":{"qq":false,"all":["google","facebook","weibo","twitter","qq","qzone","linkedin","pocket"],"douban":false,"facebook":false,"weibo":false,"instapaper":false,"whatsapp":false,"hatenaBookmark":false,"twitter":false,"messenger":false,"line":false,"vk":false,"pocket":false,"google":false,"viber":false,"stumbleupon":false,"qzone":false,"linkedin":false},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false},"anchors":{},"toggle-chapters":{},"expandable-chapters":{}},"theme":"default","author":"hzh","pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"variables":{},"title":"计算机 ,java , 大数据 基础知识体系","language":"zh-hans","gitbook":"3.2.3"},"file":{"path":"数据结构/2.图论例题.md","mtime":"2020-12-26T06:12:17.057Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2020-12-30T11:12:56.611Z"},"basePath":"..","book":{"language":""}});
        });
    </script>
</div>

        
    <script src="../gitbook/gitbook.js"></script>
    <script src="../gitbook/theme.js"></script>
    
        
        <script src="../gitbook/gitbook-plugin-splitter/splitter.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters-small/expandable-chapters-small.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-sharing-plus/buttons.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-expandable-chapters/expandable-chapters.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-toggle-chapters/toggle.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-back-to-top-button/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-code/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/jquery.mark.min.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-search-pro/search.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-pageview-count/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-livereload/plugin.js"></script>
        
    
        
        <script src="../gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
        
    

    </body>
</html>

